# Système de fichiers et recursivité

## Introduction

Les exemples de récursions présentés ici ont une forme non terminale. Ils
ne peuvent être convertis en structure itérative sans utiliser de pile (<abbr title="Dernier Entré Premier Sorti">DEPS</abbr> /
<abbr title="Last In First Out">LIFO</abbr>).


## Contenu d'un dossier — Version récursive

```python
from typing import List
import os

def listerDossierRec(dossier: str) -> List[str]:
	"""
	liste récursivement le contenu d'un dossier
	@param dossier le chemin vers le dossier à lister
	@return le contenu du dossier et de ces sous-dossiers
	précondition : dossier existe
	"""
	assert os.path.isdir(dossier) #vérification de la pré-condition
	contenu = []
	for element in os.listdir(dossier):
		chemin = os.path.join(dossier, element) #"join(/home/etu", "Cours") -> /home/etu/Cours"
		if os.path.isdir(chemin):
			contenu.append(chemin)
			contenu.extend(listerDossierRec(chemin))
	return contenu
```

Essayer et faire la trace de cette fonction.


## Commande find

La commande `find` permet (entre autres) de rechercher un fichier dans un
dossier ; en voici une version Python :

```python
from typing import List
import os

def rechercherLesFichiers(dossier: str, rech: str) -> List[str]:
	"""
	recherche les fichiers d'un dossier
	@param dossier le chemin vers le dossier à scruter
	@param rech le critère de recherche (sous-chaîne d'un nom de fichier)
	@return le chemin des fichiers trouvés
	précondition : dossier existe
	"""
	assert os.path.isdir(dossier) #vérification de la pré-condition
	trouve = []
	for element in os.listdir(dossier):
		chemin = os.path.join(dossier, element)
		if rech in element: #si le nom du fichier contien rech
			trouve.append(chemin)
		if os.path.isdir(chemin):
			trouve.extend(rechercherLesFichiers(chemin, rech))
	return trouve
```

Essayer et faire la trace de cette fonction.
- *(Expliquer la différence entre `extend` et `append`.)*


## Commande find — Variante (approfondissement)

Une variante de l'exemple précédent qui renvoie uniquement le premier fichier
trouvé, et qui n'inspecte les sous-dossiers que si c'est nécessaire :

```python
from typing import List, Optional
import os

def rechercherUnFichier(dossier: str, rech: str) -> Optional[str]:
	"""
	recherche un fichier
	@param dossier le chemin vers le dossier à scruter
	@param rech le critère de recherche (sous-chaîne d'un nom de fichier)
	@return le chemin du premier fichier trouvé
	précondition : dossier existe
	"""
	result = None
	contenu = os.listdir(dossier)
	sousDossiers = []
	i = 0
	while result == None and i < len(contenu):
		chemin = os.path.join(dossier, contenu[i])
		if rech.lower() in contenu[i].lower():
			result = chemin
		elif os.path.isdir(chemin):
			sousDossiers.append(chemin) #on mémorise le sous-dossier pour la recherche récursive
		i += 1
	
	if result == None: #non trouvé dans le dossier courant
		i = 0
		while result == None and i < len(sousDossiers):
			result = rechercherUnFichier(sousDossiers[i], rech)
			i += 1
			
	return result
```

- Essayer et faire la trace de cette fonction et comparer son fonctionnement
à la précédente (`rechercherLesFichiers`).
- *(Expliquer le type `Optional`.)*


## Contenu d'un dossier — Version itérative (approfondissement)

Cet exemple reprend le parcours d'un dossier, mais dans une version itérative
(en utilisant une pile DEPS / LIFO) — implémentée sous la forme d'un tableau  :

```python
from typing import List
import os

def listerDossierIte(dossier: str) -> str:
	assert os.path.isdir(dossier)
	dossiers = [dossier]					#pile LIFO
	contenu = []
	while len(dossiers) != 0:				#tant que la pile n'est pas vide
											#tant qu'il reste des dossiers à traiter
		dossier = dossiers.pop()			#dépiler (enlève et renvoie le dernier)
		for element in os.listdir(dossier):
			chemin = os.path.join(dossier, element)
			contenu.append(chemin)
			if os.path.isdir(chemin):
				dossiers.append(chemin)		#empiler le dossier à traiter (ultérieurement)
	return contenu
```

- Essayer et faire la trace de cette fonction et comparer son fonctionnement
à la version récursive (`listerDossierRec`).